package LC;

/**
 * https://leetcode.com/problems/search-insert-position/description/
 * Given a sorted array and a target value,
 * return the index if the target is found.
 * If not, return the index where it would be if it were inserted in order.
 * You may assume no duplicates in the array.
 * Here are few examples.
 * [1,3,5,6], 5 → 2
 * [1,3,5,6], 2 → 1
 * [1,3,5,6], 7 → 4
 * [1,3,5,6], 0 → 0
 */
public class LC_035_SearchInsertPosition_BinarySearch_Array_Recur_TwoPointers {
    public static void main(String[] args) {
        int[] a = {1, 3, 4, 5, 6, 7, 9};
        int target = 2;
        int idx = Solution.searchInsert(a, target);
        System.out.println(idx);
    }

    static class Solution {
        static int searchInsert(int[] nums, int target) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        private static int binarySearch(int[] nums, int target, int left, int right) {
            if (left > right) {
                return -1;
            }
            //插入的位置
            if (left == right) {
                if (nums[left] >= target) return left;
                else return right + 1;
            }

            int mid = (left + right) / 2;

            if (target < nums[mid]) {
                return binarySearch(nums, target, left, mid);
            } else if (target == nums[mid]) {
                return mid;
            } else {
                return binarySearch(nums, target, mid + 1, right);
            }
        }
    }
}
